#!/usr/bin/env python3
# -*- coding: utf-8 -*-
"""
队列（Queue）的Python实现
包含基本操作：enqueue, dequeue, front, is_empty, size
以及一些实际应用示例
"""

from collections import deque

class Queue:
    """队列类实现"""
    
    def __init__(self):
        """初始化空队列"""
        self.items = deque()
    
    def enqueue(self, item):
        """
        入队操作
        Args:
            item: 要入队的元素
        """
        self.items.append(item)
        print(f"入队: {item}")
    
    def dequeue(self):
        """
        出队操作
        Returns:
            队头元素
        Raises:
            IndexError: 当队列为空时抛出异常
        """
        if not self.is_empty():
            item = self.items.popleft()
            print(f"出队: {item}")
            return item
        raise IndexError("队列为空，无法出队")
    
    def front(self):
        """
        查看队头元素（不删除）
        Returns:
            队头元素
        Raises:
            IndexError: 当队列为空时抛出异常
        """
        if not self.is_empty():
            return self.items[0]
        raise IndexError("队列为空，无法查看队头")
    
    def is_empty(self):
        """
        判断队列是否为空
        Returns:
            bool: True表示空，False表示非空
        """
        return len(self.items) == 0
    
    def size(self):
        """
        获取队列的大小
        Returns:
            int: 队列中元素个数
        """
        return len(self.items)
    
    def clear(self):
        """清空队列"""
        self.items.clear()
        print("队列已清空")
    
    def __str__(self):
        """字符串表示"""
        return f"Queue({list(self.items)})"
    
    def __len__(self):
        """长度表示"""
        return len(self.items)


class CircularQueue:
    """循环队列实现"""
    
    def __init__(self, capacity):
        """
        初始化循环队列
        Args:
            capacity: 队列容量
        """
        self.capacity = capacity
        self.queue = [None] * capacity
        self.front = 0
        self.rear = 0
        self.size = 0
    
    def enqueue(self, item):
        """入队"""
        if self.is_full():
            raise OverflowError("队列已满")
        
        self.queue[self.rear] = item
        self.rear = (self.rear + 1) % self.capacity
        self.size += 1
        print(f"入队: {item}")
    
    def dequeue(self):
        """出队"""
        if self.is_empty():
            raise IndexError("队列为空")
        
        item = self.queue[self.front]
        self.queue[self.front] = None
        self.front = (self.front + 1) % self.capacity
        self.size -= 1
        print(f"出队: {item}")
        return item
    
    def is_empty(self):
        """判断队列是否为空"""
        return self.size == 0
    
    def is_full(self):
        """判断队列是否已满"""
        return self.size == self.capacity
    
    def get_size(self):
        """获取队列大小"""
        return self.size
    
    def __str__(self):
        """字符串表示"""
        items = []
        for i in range(self.size):
            idx = (self.front + i) % self.capacity
            items.append(self.queue[idx])
        return f"CircularQueue({items})"


def test_basic_operations():
    """测试基本操作"""
    print("=" * 50)
    print("测试队列的基本操作")
    print("=" * 50)
    
    queue = Queue()
    
    # 测试空队列
    print(f"队列是否为空: {queue.is_empty()}")
    print(f"队列的大小: {queue.size()}")
    
    # 入队操作
    print("\n--- 入队操作 ---")
    queue.enqueue(1)
    queue.enqueue(2)
    queue.enqueue(3)
    queue.enqueue("hello")
    queue.enqueue([4, 5, 6])
    
    print(f"当前队列: {queue}")
    print(f"队列的大小: {queue.size()}")
    print(f"队头元素: {queue.front()}")
    
    # 出队操作
    print("\n--- 出队操作 ---")
    while not queue.is_empty():
        try:
            queue.dequeue()
            print(f"当前队列: {queue}")
        except IndexError as e:
            print(f"错误: {e}")
    
    print(f"队列是否为空: {queue.is_empty()}")


def test_circular_queue():
    """测试循环队列"""
    print("\n" + "=" * 50)
    print("测试循环队列")
    print("=" * 50)
    
    cq = CircularQueue(3)
    
    # 入队操作
    cq.enqueue(1)
    cq.enqueue(2)
    cq.enqueue(3)
    print(f"当前队列: {cq}")
    
    # 出队一个元素
    cq.dequeue()
    print(f"出队后: {cq}")
    
    # 继续入队
    cq.enqueue(4)
    print(f"入队4后: {cq}")
    
    # 全部出队
    while not cq.is_empty():
        cq.dequeue()
        print(f"当前队列: {cq}")


def test_task_scheduler():
    """测试任务调度器"""
    print("\n" + "=" * 50)
    print("测试任务调度器")
    print("=" * 50)
    
    class TaskScheduler:
        def __init__(self):
            self.task_queue = Queue()
        
        def submit_task(self, task):
            """提交任务"""
            self.task_queue.enqueue(task)
            print(f"任务已提交: {task}")
        
        def execute_next_task(self):
            """执行下一个任务"""
            if not self.task_queue.is_empty():
                task = self.task_queue.dequeue()
                print(f"正在执行: {task}")
                return task
            else:
                print("没有待执行的任务")
                return None
    
    # 测试任务调度器
    scheduler = TaskScheduler()
    scheduler.submit_task("任务A")
    scheduler.submit_task("任务B")
    scheduler.submit_task("任务C")
    
    scheduler.execute_next_task()  # 执行任务A
    scheduler.execute_next_task()  # 执行任务B


def test_bfs():
    """测试广度优先搜索"""
    print("\n" + "=" * 50)
    print("测试广度优先搜索")
    print("=" * 50)
    
    def bfs(graph, start):
        visited = set()
        queue = deque([start])
        visited.add(start)
        result = []
        
        while queue:
            vertex = queue.popleft()
            result.append(vertex)
            
            for neighbor in graph[vertex]:
                if neighbor not in visited:
                    visited.add(neighbor)
                    queue.append(neighbor)
        
        return result
    
    # 示例图
    graph = {
        'A': ['B', 'C'],
        'B': ['A', 'D', 'E'],
        'C': ['A', 'F'],
        'D': ['B'],
        'E': ['B', 'F'],
        'F': ['C', 'E']
    }
    
    result = bfs(graph, 'A')
    print(f"BFS遍历结果: {result}")


def main():
    """主函数"""
    print("队列（Queue）数据结构演示程序")
    print("=" * 50)
    
    # 运行所有测试
    test_basic_operations()
    test_circular_queue()
    test_task_scheduler()
    test_bfs()
    
    print("\n" + "=" * 50)
    print("所有测试完成！")
    print("=" * 50)


if __name__ == "__main__":
    main()
